#include <iostream>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

typedef struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
} ListNode;

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (!l1 && !l2) return NULL;

        ListNode *head = new ListNode(-1);
        ListNode *lptr, *rptr, *tail = head;
        int carry = 0;

        for (lptr = l1, rptr = l2; lptr && rptr;
             lptr = lptr->next, rptr = rptr->next) {
            tail->next = bitAddition(lptr, rptr, carry);
            tail = tail->next;
        }

        if (!lptr && rptr) {
            tail->next = deepCpyNodeList(rptr, carry);
            tail = tail->next;
        } else if (lptr && !rptr) {
            tail->next = deepCpyNodeList(lptr, carry);
            tail = tail->next;
        } else {
          if (carry) {
            tail->next = new ListNode(carry);
          }
        }


        return head->next;
    }

private:
    ListNode *bitAddition(ListNode *l1, ListNode *l2, int &carry) {
        int sum = l1->val + l2->val + carry;
        carry = sum / 10;
        sum %= 10;

        return new ListNode(sum);
    }

    ListNode *deepCpyNodeList(ListNode *l, int &carry) {
        ListNode *head = new ListNode(-1);
        ListNode *tail = head;

        for (ListNode *ptr = l; ptr; ptr = ptr->next) {
            tail->next = new ListNode(carry + ptr->val);
            carry = (carry + ptr->val) / 10;
            tail->next->val %= 10;
            tail = tail->next;
        }

        if (carry) {
          tail->next = new ListNode(carry);
        }

        return head->next;
    }
};

void dumpLinkedList(ListNode *l)
{
  cout<<"dump linked list:";
  for (ListNode *ptr = l; ptr; ptr = ptr->next) {
    cout<<" "<<ptr->val;
  }
  cout<<endl;
}

int main()
{
  ListNode *l1 = new ListNode(2);
  ListNode *l2 = new ListNode(8);
  l2->next = new ListNode(9);
  l2->next->next = new ListNode(9);

  Solution solution;
  ListNode *ret = solution.addTwoNumbers(l1, l2);

  dumpLinkedList(ret);

  return 0;
}
